package leetcode_zh

import (
	"math"
)

/**
 * @Description: 105. 从前序与中序遍历序列构造二叉树 中等
 * @Keyword: 中左右 左右中 递归 计算好左子树，右子树区间
 * @Author: kami
 * @Date: 2022/5/27 18:35
 **/
func buildTree(preorder []int, inorder []int) *TreeNode {
	preLen := len(preorder)
	inLen := len(inorder)
	inMap := make(map[int]int, inLen)
	for i := 0; i < inLen; i++ {
		inMap[inorder[i]] = i
	}
	return buildTreeDfs105(preorder, 0, preLen-1, 0, inLen-1, inMap)
}

func buildTreeDfs105(preorder []int, preLeft, preRight, inLeft, inRight int, inMap map[int]int) *TreeNode {
	if preLeft > preRight || inLeft > inRight {
		return nil
	}
	rootVal := preorder[preLeft]
	root := &TreeNode{
		Val: rootVal,
	}
	PIndex := inMap[rootVal]
	root.Left = buildTreeDfs105(preorder, preLeft+1, PIndex-inLeft+preLeft, inLeft, PIndex-1, inMap)
	root.Right = buildTreeDfs105(preorder, PIndex-inLeft+preLeft+1, preRight, PIndex+1, inRight, inMap)
	return root
}

/**
 * @Description: 06. 从中序与后序遍历序列构造二叉树 中等
 * @Keyword: 递归，根据长度计算下标
 * @Author: kami
 * @Date: 2022/5/27 20:02
 **/
func buildTree86(inorder []int, postorder []int) *TreeNode {
	postLen := len(postorder)
	inLen := len(inorder)
	inMap := make(map[int]int, inLen)
	for i := 0; i < inLen; i++ {
		inMap[inorder[i]] = i
	}
	return buildTreeDfs06(postorder, 0, postLen-1, 0, inLen-1, inMap)
}

func buildTreeDfs06(postorder []int, postLeft, postRight, inLeft, inRight int, inMap map[int]int) *TreeNode {
	if postLeft >= postRight || inLeft >= inRight {
		return nil
	}
	mid := postorder[postRight]
	root := &TreeNode{
		Val: mid,
	}
	midIdx := inMap[mid]
	root.Left = buildTreeDfs06(postorder, postLeft, midIdx-1-inLeft+postLeft, inLeft, midIdx-1, inMap)
	root.Right = buildTreeDfs06(postorder, midIdx-inLeft+postLeft, postRight-1, midIdx+1, inRight, inMap)

	return root
}

/**
 * @Description: 103. 二叉树的锯齿形层序遍历 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/5/31 19:03
 **/
func zigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	var direction = true // true从左往右，false从右往左
	var res [][]int
	var curLevelNodes = []*TreeNode{root}
	for len(curLevelNodes) > 0 {
		var curNodes []*TreeNode
		var curRes []int
		var n = len(curLevelNodes)
		if direction {
			for i := 0; i < n; i++ {
				curRes = append(curRes, curLevelNodes[i].Val)
				if curLevelNodes[i].Left != nil {
					curNodes = append(curNodes, curLevelNodes[i].Left)
				}
				if curLevelNodes[i].Right != nil {
					curNodes = append(curNodes, curLevelNodes[i].Right)
				}
			}
		} else {
			for i := 0; i < n; i++ {
				curRes = append(curRes, curLevelNodes[n-1-i].Val)
				if curLevelNodes[i].Left != nil {
					curNodes = append(curNodes, curLevelNodes[i].Left)
				}
				if curLevelNodes[i].Right != nil {
					curNodes = append(curNodes, curLevelNodes[i].Right)
				}
			}
		}
		direction = !direction
		curLevelNodes = curNodes
		res = append(res, curRes)
	}
	return res
}

/**
 * @Description: 95. 不同的二叉搜索树 II
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/1 7:54
 **/
func generateTrees(n int) []*TreeNode {
	if n <= 0 {
		return []*TreeNode{}
	}
	return generate95(1, n)
}

func generate95(left, right int) []*TreeNode {
	if left > right {
		return []*TreeNode{nil}
	}
	var res []*TreeNode
	for i := left; i <= right; i++ {
		var leftNodes = generate95(left, i-1)
		var rightNodes = generate95(i+1, right)
		for _, nodeL := range leftNodes {
			for _, nodeR := range rightNodes {
				var cur = &TreeNode{Val: i}
				cur.Left = nodeL
				cur.Right = nodeR
				res = append(res, cur)
			}
		}
	}
	return res
}

/**
 * @Description: 98. 验证二叉搜索树 中等
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/6/5 18:34
 **/
func isValidBST(root *TreeNode) bool {
	return helper(root, math.MinInt64, math.MaxInt64)
}

func helper(root *TreeNode, lower, upper int) bool {
	if root == nil {
		return true
	}
	if root.Val <= lower || root.Val >= upper {
		return false
	}
	return helper(root.Left, lower, root.Val) && helper(root.Right, root.Val, upper)
}

/**
 * @Description: 98. 验证二叉搜索树 中等
 * @Keyword: 中序变例要升序
 * @Author: kami
 * @Date: 2022/6/5 18:34
 **/
func isValidBST98(root *TreeNode) bool {
	stack := []*TreeNode{}
	inorder := math.MinInt64
	for len(stack) > 0 || root != nil {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if root.Val <= inorder {
			return false
		}
		inorder = root.Val
		root = root.Right
	}
	return true
}

/**
 * @Description: 98. 验证二叉搜索树 中等
 * @Keyword: 中序便利
 * @Author: kami
 * @Date: 2022/6/5 18:34
 **/
var pre = math.MinInt32

func isValidBST_98pre(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return isValidBST_pre(root)
}

func isValidBST_pre(root *TreeNode) bool {
	if root == nil {
		return true
	}
	// 访问左子树
	if !isValidBST_pre(root.Left) {
		return false
	}
	// 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
	if root.Val <= pre {
		return false
	}
	pre = root.Val
	// 访问右子树
	return isValidBST_pre(root.Right)
}

/**
 * @Description: 114. 二叉树展开为链表 中等
 * @Keyword: 前序遍历的顺序改造为单链表
 * @Author: kami
 * @Date: 2022/6/7 22:59
 **/
func flatten(root *TreeNode) {
	if root == nil {
		return
	}
	var nodes []*TreeNode
	var head = root
	nodes = firstSearchDfs(root, nodes)
	for i := 1; i < len(nodes); i++ {
		head.Left = nil
		head.Right = nodes[i]
		head = nodes[i]
	}
}

/**
 * @Description: 114. 二叉树展开为链表 中等
 * @Keyword: 对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，将当前节点的右子节点赋给前驱节点的右子节点，
			 然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。
			 对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束。
 * @Author: kami
 * @Date: 2022/6/8 9:31
 **/
func flatten_v2(root *TreeNode) {
	curr := root
	for curr != nil {
		if curr.Left != nil {
			next := curr.Left
			predecessor := next
			for predecessor.Right != nil {
				predecessor = predecessor.Right
			}
			predecessor.Right = curr.Right
			curr.Left, curr.Right = nil, next
		}
		curr = curr.Right
	}
}

func firstSearchDfs(node *TreeNode, res []*TreeNode) []*TreeNode {
	if node == nil {
		return res
	}
	res = append(res, node)
	res = firstSearchDfs(node.Left, res)
	res = firstSearchDfs(node.Right, res)
	return res
}

/**
 * @Description: 617. 合并二叉树 简单
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/6/11 16:55
 **/
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	var node *TreeNode
	if root1 == nil && root2 == nil {
		return node
	}
	if root1 != nil && root2 != nil {
		node = &TreeNode{
			Val:   root1.Val + root2.Val,
			Left:  mergeTrees(root1.Left, root2.Left),
			Right: mergeTrees(root1.Right, root2.Right),
		}
		return node
	}
	if root1 != nil {
		node = &TreeNode{
			Val:   root1.Val,
			Left:  mergeTrees(root1.Left, nil),
			Right: mergeTrees(root1.Right, nil),
		}
		return node
	}
	if root2 != nil {
		node = &TreeNode{
			Val:   root2.Val,
			Left:  mergeTrees(nil, root2.Left),
			Right: mergeTrees(nil, root2.Right),
		}
		return node
	}
	return node
}

/**
 * @Description: 543. 二叉树的直径 简单
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/6/12 9:20
 **/
func diameterOfBinaryTree(root *TreeNode) int {
	maxDia := 0
	if root == nil {
		return maxDia
	}
	var dfs func(*TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		lh := dfs(node.Left)
		rh := dfs(node.Right)
		maxDia = getMax(maxDia, lh+rh)
		return 1 + getMax(lh, rh)
	}
	dfs(root)
	return maxDia
}

/**
 * @Description: 226. 翻转二叉树 简单
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/6/12 12:17
 **/
func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	left := invertTree(root.Left)
	right := invertTree(root.Right)
	root.Left = right
	root.Right = left
	return root
}

/**
* @Description: 538. 把二叉搜索树转换为累加树 中等
* @Keyword: BST的中序遍历就是从小到大,那么反过来就是从大到小,然后累加就好了.
    以右->根->左的顺序遍历二叉树，将遍历顺序的前一个结点的累加值记录起来，和当前结点相加，得到当前结点的累加值。
* @Author: kami
* @Date: 2022/6/12 13:39
**/
func convertBST(root *TreeNode) *TreeNode {
	num := 0
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node != nil {
			//遍历右子树
			dfs(node.Right)
			//遍历顶点
			node.Val = node.Val + num
			num = node.Val
			//遍历左子树
			dfs(node.Left)
			return
		}
		return
	}

	dfs(root)

	return root
}

/**
 * @Description: 124. 二叉树中的最大路径和 困难
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/6/14 12:01
 **/
func maxPathSum(root *TreeNode) int {
	var max = root.Val

	var getMaxPath func(node *TreeNode) int
	getMaxPath = func(node *TreeNode) int {
		if node == nil {
			return 0
		}

		var left = getMax(0, getMaxPath(node.Left))
		var right = getMax(0, getMaxPath(node.Right))

		max = getMax(max, node.Val+left+right)

		return getMax(left, right) + node.Val
	}
	getMaxPath(root)
	return max
}

/**
 * @Description: 437. 路径总和 III 中等
 * @Keyword: 前缀和
 * @Author: kami
 * @Date: 2022/6/14 17:24
 **/
func pathSum(root *TreeNode, targetSum int) int {
	var ans int
	preSum := map[int64]int{0: 1}
	var dfs func(*TreeNode, int64)
	dfs = func(node *TreeNode, curr int64) {
		if node == nil {
			return
		}
		// 累加前缀和
		curr += int64(node.Val)
		// 如果前缀和中有出现某个节点的前缀和 = 当前前缀和 - targetSum，比如前面的一个前缀和 5 = 当前前缀和10 - 目标值5
		ans += preSum[curr-int64(targetSum)]
		// 前缀和次数加1
		preSum[curr]++
		dfs(node.Left, curr)
		dfs(node.Right, curr)
		// 前缀和次数减1
		preSum[curr]--
		return
	}

	dfs(root, 0)

	return ans

}

/**
 * @Description: 437. 路径总和 III 中等
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/6/14 17:24
 **/
func pathSum437(root *TreeNode, targetSum int) int {
	if root == nil {
		return 0
	}
	res := rootSum(root, targetSum)
	res += pathSum437(root.Left, targetSum)
	res += pathSum437(root.Right, targetSum)
	return res
}

func rootSum(root *TreeNode, targetSum int) (res int) {
	if root == nil {
		return
	}
	val := root.Val
	if val == targetSum {
		res++
	}
	res += rootSum(root.Left, targetSum-val)
	res += rootSum(root.Right, targetSum-val)
	return
}

/**
 * @Description: 236. 二叉树的最近公共祖先 中等
 * @Keyword:递归寻找
 * @Author: kami
 * @Date: 2022/6/16 14:56
 **/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	// LCA 问题
	if root == nil || root == p || root == q {
		return root
	}
	// 左右子树是否包含目标节点
	var left = lowestCommonAncestor(root.Left, p, q)
	var right = lowestCommonAncestor(root.Right, p, q)

	// 如果 当前节点左子树包含一个，右子树包含一个，则当前节点就是最近祖先
	if left != nil && right != nil {
		return root
	}
	if left != nil {
		return left
	}
	if right != nil {
		return right
	}

	return nil
}

/**
 * @Description: 236. 二叉树的最近公共祖先 中等
 * @Keyword: 父节点
 * @Author: kami
 * @Date: 2022/6/16 14:56
 **/
func lowestCommonAncestor236(root, p, q *TreeNode) *TreeNode {
	// 单签节点的父亲节点
	parent := map[int]*TreeNode{}
	visited := map[int]bool{}

	var dfs func(*TreeNode)
	dfs = func(r *TreeNode) {
		if r == nil {
			return
		}
		if r.Left != nil {
			parent[r.Left.Val] = r
			dfs(r.Left)
		}
		if r.Right != nil {
			parent[r.Right.Val] = r
			dfs(r.Right)
		}
	}

	dfs(root)

	// P的父节点都设置为true
	for p != nil {
		visited[p.Val] = true
		p = parent[p.Val]
	}
	// 在q的父节点中找到一级级找共同父节点
	for q != nil {
		if visited[q.Val] {
			return q
		}
		q = parent[q.Val]
	}

	return nil
}
